#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "dfg.h"
#include "error.h"
#include "list.h"
#include "inter_code.h"
#include "gp_list.h"
#include "common.h"
#include "sym_table.h"

static bb_t *__new_bb(struct list_head *head); 

dfg_t *new_dfg(void)
{
	dfg_t *dfg = calloc(1, sizeof(dfg_t));	
	if(!dfg){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
	}
	INIT_LIST_HEAD(&dfg->bbs_head);
	return dfg;
}


/*
	标识“首指令”

	满足任何1个条件就可以：
	1 第一条指令；
	2 紧跟（条件）跳转指令之后的指令；
	3 （条件）跳转指令的目标指令；
	另外，添加了 entry 和 exit, 它们也是首指令
*/
void mark_first(struct list_head *head)
{
    if(!head)
        return;
	int len = get_list_len(head);
    // Entry +  Exit 就占了 2 个指令
	assert(len >= 2); 
	// 标记 Entry 与 Exit	
	inter_inst_t *inst;
	inter_inst_t *next_inst;
	inst = container_of(head->next, 
            inter_inst_t, entry); // Entry
	inst->first_inst = true;

	inst = container_of(head->prev, 
            inter_inst_t, entry); // Exit
	inst->first_inst = true;

	if(len > 2) {
        // 实际的第一条指令
		inst = container_of(head->next->next, 
                inter_inst_t, entry); 
		inst->first_inst = true;
	}

	list_for_each_entry(inst, head, entry){
		if(inter_inst_is_jump(inst) || 
                inter_inst_is_cond_jump(inst)){
            // 跳转指令的目标指令是首指令
			inst->jmp_target->first_inst = true; 
			next_inst = container_of(inst->entry.next, 
                    inter_inst_t, entry);
            // 紧跟跳转指令之后的指令是首指令
			next_inst->first_inst = true;
		}
	}
}


/*
	@head   fun_t.inter_code(必须标记过首指令)
	@dfg    要加入的流图
*/
void create_bbs(struct list_head *head, dfg_t *dfg)
{
	if(!head || !dfg)
		return;

	LIST_HEAD(tmp);  // 定义临时链表
	inter_inst_t *inst;
	bb_t *bb = NULL;
    // 依次取出每一条指令
	list_for_each_entry(inst, head, entry){ 
		if(list_empty(&tmp) && inst->first_inst){
            // 添加第一条首指令到临时链表
			list_add_tail(&inst->entry_in_bb, &tmp); 
			continue;
		}

		if(!list_empty(&tmp)){
			if(inst->first_inst){  // 发现新的首指令
                // 前面的指令构成基本块
				bb = __new_bb(&tmp); 
                // 把基本块添加到流图
                list_add_tail(&bb->entry_in_dfg, 
                        &dfg->bbs_head); 
			}
            // 添加新的首指令或者基本块后继的指令
			list_add_tail(&inst->entry_in_bb, &tmp); 
		}
	}

	bb = __new_bb(&tmp); // 前面剩下的指令构成基本块
    // 添加最后一个基本块到流图
    list_add_tail(&bb->entry_in_dfg, &dfg->bbs_head); 
}


/*
    创建基本块
    head：临时链表的头节点，此链表缓存了一个基本块的所有指令
*/

bb_t *__new_bb(struct list_head *head) 
{
	if(!head)
		return NULL;

    if(list_empty(head))
        return NULL;

	static int bb_id = 0;
	
	bb_t *bb = calloc(1, sizeof(bb_t));			
	if(!bb){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
	}
	bb->visited = false;
	bb->reach = true;
	bb->id  = bb_id++;
	
	INIT_LIST_HEAD(&bb->insts_head);
	INIT_LIST_HEAD(&bb->prede_head);
	INIT_LIST_HEAD(&bb->suc_head);

	struct list_head *cur, *next;
	inter_inst_t *inst;
	list_for_each_safe(cur, next, head){
		list_del(cur); // 从临时的链表删除之
        // 添加到新创建的基本块
		list_add_tail(cur, &bb->insts_head); 
		inst = container_of(cur, inter_inst_t, entry_in_bb);
		inst->in_bb = bb;
	}

	return bb;
}


// 获得基本块的最后一条指令
inter_inst_t * get_last_inst(bb_t *bb)
{
	if(!bb)
		return NULL;
	if(list_empty(&bb->insts_head))
		return NULL;

	inter_inst_t *inst = container_of(bb->insts_head.prev, 
                inter_inst_t, entry_in_bb);
	return inst;
}


// head: 基本块链表的头节点,也就是 dfg_t 的 &bbs_head
        /*
            边的分类：
            1. 条件跳转边  if(xxx) goto B ;   A->B
            2. 无条件跳转边  goto B ;         A->B
            3. 顺序执行边,  A是普通指令        A->B
            4. fall-through 边, 当情况1为假   A->C

        */
void link_bbs(struct list_head *head)
{
    if(!head)
        return;
	bb_t *bb, *next_bb, *tgt_bb;
	inter_inst_t *inst;
	
	list_for_each_entry(bb, head, entry_in_dfg){
		inst = get_last_inst(bb); 

		// 情况 3-4， 最后一个bb排除掉，因为它没有后继
		if(!inter_inst_is_jump(inst) && 
                bb->entry_in_dfg.next != head) {  
            
			next_bb = container_of(bb->entry_in_dfg.next, 
                    bb_t, entry_in_dfg);
            // 添加后继	
			gp_node_add_tail(next_bb, &bb->suc_head); 
            // 添加前驱
			gp_node_add_tail(bb, &next_bb->prede_head); 
		}
		// 是直接或者条件跳转,情况 1-2
		if(inter_inst_is_jump(inst) || 
                inter_inst_is_cond_jump(inst)) {
			tgt_bb = inst->jmp_target->in_bb;
            // 添加后继
			gp_node_add_tail(tgt_bb, &bb->suc_head); 
            // 添加前驱
			gp_node_add_tail(bb, &tgt_bb->prede_head); 
		}	
	}
}

void create_dfg(fun_t *fun)
{
    if(!fun || !fun->dfg)
        return;

	mark_first(&fun->inter_code);
	create_bbs(&fun->inter_code, fun->dfg);
	link_bbs(&fun->dfg->bbs_head);
}

void destroy_bbs(struct list_head *head)
{
    bb_t *cur, *next; 
	list_for_each_entry_safe(cur, next, head, entry_in_dfg){ 
        gp_list_free(&cur->prede_head);
        gp_list_free(&cur->suc_head);
        // cur->insts_head 不用释放
		list_del(&cur->entry_in_dfg); 
		free(cur);  
	}
}


// 从入口开始是否可以到达
// 思路：找到 block 的前驱，测试前驱是否可达；
// 递归出口：前驱是第一个block，说明从入口开始可以到达，返回 true
// head 是链表的头, bb 指向要测试的 block

static bool __reachable(struct list_head *head, bb_t *bb)
{
	if(!head || !bb){
		SYSTEM_FATAL_ERR(POINTER_IS_NULL);
	}

	if(head->next == &bb->entry_in_dfg) // 说明是第一个 block
		return true;

	if(bb->visited)
		return false; // 访问过了,构成了环,也判定为不可达

	bb->visited = true; // 标记已经访问

	bool can_reach = false;
	bb_t *prede;
	gp_node_t *node;  // 若有前驱,测试每个前驱
	list_for_each_entry(node, &bb->prede_head, entry){
		prede = (bb_t *)node->addr;
		can_reach = __reachable(head, prede); // 递归测试
		if(can_reach)
			break; // 可从入口到达,终止测试;否则继续测试其他前驱
	}
	return can_reach;
}


static void __reset_visit(struct list_head *head)
{
	if(!head){
		SYSTEM_FATAL_ERR(POINTER_IS_NULL);
	}
	bb_t *bb;
	list_for_each_entry(bb, head, entry_in_dfg){
		bb->visited = false;
	}
}

bool reachable(struct list_head *head, bb_t *bb)
{
	__reset_visit(head);	
	return __reachable(head, bb);
}



// 删除 prede 到 suc 的边，并且评估 suc 的可达性，不可达会继续删除 suc 发出的边
void kill_link(bb_t *prede, bb_t *suc, struct list_head *head)
{
	if(!prede || !suc || !head){
		SYSTEM_FATAL_ERR(POINTER_IS_NULL);
	}

	gp_node_t *node, *next_node; 

	// 先找到某个 suc， 再删除之
	list_for_each_entry(node, &prede->suc_head, entry){
		if(node->addr == (void*)suc){
			list_del(&node->entry);
			free(node);
			break;			
		}		
	}

	// 先找到某个 prede， 再删除之
	list_for_each_entry(node, &suc->prede_head, entry){
		if(node->addr == (void*)prede){
			list_del(&node->entry);
			free(node);
			break;			
		}		
	}

    // 因为从 prede 到 suc 的边删除了，suc 的可达性要重新评估
	// 测试 suc 是否可达，如果不可达，
	// 从它发出的关联也是无效的，还要删除这些关联
	if(!reachable(head, suc)){
		// printf("%d 不可达\n", suc->id );	

/*

	没有用safe导致跑飞
	这个错误十分隐蔽，调用 kill_link 的时候会删除 node, 
	kill_link 返回后，从 node 的下一个节点继续遍历,
	可是node的内存都释放了，肯定跑飞；
	所以，用 next_node 提前保存好 node 的下一个节点
	纸上得来终觉浅，绝知此事要躬行
*/		
		list_for_each_entry_safe(node, next_node, &suc->suc_head, entry){
			kill_link(suc, (bb_t *)node->addr, head);  // 递归
		}
	}
}

// 这个函数的作用是删除某个 block 的所有前驱和后继关系
//  
//    a ---> b ---> c
// 删除 a 到 b, b 到 c 的关系    
// 删除上面 2 条边

void kill_all_links(bb_t *block, struct list_head *head)
{
	if(!block){
		SYSTEM_FATAL_ERR(POINTER_IS_NULL);
	}
		
	gp_node_t *node, *next_node; 
	list_for_each_entry_safe(node, next_node, &block->prede_head, entry){
		kill_link(node->addr, block, head);
	}

	list_for_each_entry_safe(node, next_node, &block->suc_head, entry){
		kill_link(block, node->addr, head);
	}
}


// 即使没有用任何优化方法也可以用此函数
// 例如新手写出的明显有死代码的代码
// 可以调用此函数消除死代码
void remove_unreachable_block(struct list_head *head)
{
	if(!head)
		return;
	
	bb_t *bb;	
	list_for_each_entry(bb, head, entry_in_dfg) {
		if(!reachable(head, bb)) {
		//	printf("bb %d 不可达\n", bb->id);
			bb->reach = false; //记录块不可达
			kill_all_links(bb, head); 
		}
	}
}


void print_dfg(fun_t *fun)
{
	struct list_head *head = &fun->dfg->bbs_head;
	bb_t *bb;
	gp_node_t *node;
	list_for_each_entry(bb, head, entry_in_dfg){
		if(bb->reach) {
			printf("\n==========  Block: %d  =====\n", bb->id);
		} else {
			printf("\n============== Block: %d 【不可达】 =============\n", bb->id);

		}
		printf("前驱：");
		list_for_each_entry(node, &bb->prede_head, entry) {
			printf("%d, ", ((bb_t *)node->addr)->id); 
		}
		printf("\b\b; ");
		printf("后继：");
		list_for_each_entry(node, &bb->suc_head, entry) {
			printf("%d, ", ((bb_t *)node->addr)->id); 
		}
		printf("\b\b  \n\n");
		inter_inst_t *pos;
		list_for_each_entry(pos, &bb->insts_head, entry_in_bb){
			inter_inst_to_string(pos);
		}
		printf("===========================\n\n");
	}
}


void print_dfg_dot(fun_t *fun)
{
	printf("digraph %s {\n", fun->name);
	printf("node [shape=rectangle];\n");

	struct list_head *head = &fun->dfg->bbs_head;
	bb_t *bb;
	gp_node_t *suc_node;
	list_for_each_entry(bb, head, entry_in_dfg){
	//	if(!bb->reach)
	//		continue;   如果加上这 2 行，dot 图中不再显示孤立的节点

		// b0 [label= "B0\n
		printf("b%d [label=\"B%d\\n",  bb->id,  bb->id);

		inter_inst_t *pos;
		list_for_each_entry(pos, &bb->insts_head, entry_in_bb){
			inter_inst_to_dot_string(pos);
		}
		printf("\"]\n");

		if(bb->entry_in_dfg.prev == head  || bb->entry_in_dfg.next == head) { // 入口和出口
			printf("b%d[shape=Msquare];\n", bb->id);
		} 

		list_for_each_entry(suc_node, &bb->suc_head, entry) {
			printf("b%d -> b%d;\n", bb->id, ((bb_t *)suc_node->addr)->id); 
		}
	}

	printf("}\n");
}

int extract_reachable_code(struct list_head *bbs_head, struct list_head *code_out)
{
	int inst_cnt  = 0;
	if(!bbs_head || !code_out)
		return -1;
	if(!list_empty(code_out)) {
		printf("链表不为空！先清空\n");
		gp_list_free(code_out);
	}
	bb_t *bb;
	inter_inst_t *inst;	
	
	list_for_each_entry(bb, bbs_head, entry_in_dfg) {
		if(bb->reach) {
			list_for_each_entry(inst, &bb->insts_head, entry_in_bb) {					
				gp_node_add_tail(inst, code_out); //抽取有效指令
				inst_cnt++;
			}
		} 
	}
	return inst_cnt;
}

void optimize_funs(void)
{
  	fun_t *cur;
	unsigned bkt;
	hash_for_each(sym_tab_g.fun_tab, bkt, cur, hnode) {
        if(cur->is_ext)
            continue;
        create_dfg(cur);
        print_dfg(cur);
		print_dfg_dot(cur);
        remove_unreachable_block(&cur->dfg->bbs_head); // 清理多余的 block
		
        print_dfg(cur);
		print_dfg_dot(cur);
		LIST_HEAD(tmp_list);
		extract_reachable_code(&cur->dfg->bbs_head, &tmp_list); // 抽取有效代码
		print_optimized_code(&tmp_list); // 打印抽取后的代码
		gp_list_free(&tmp_list);
	}	
}